package test1;

import java.util.Scanner;

public class Solution2 {//假币问题 - 减常量因子的减治法
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入硬币数量：");
        int num = sc.nextInt();
        if (num == 1){
            System.out.println("一枚硬币无法比较！" + "\n" + "请输入正确的硬币数量！");
            return;
        }
        int[] coins = new int[num + 1];
        coins[0] = num; //0号数组存储硬币数
        System.out.println("请输入所有的硬币：");
        for (int i = 1; i <= num; i++) {
            coins[i] = sc.nextInt();
        }
        int[] res = findFakeCoin(coins, 1);
        System.out.println("第" + res[0] + "枚硬币为假币");
    }

    private static int[] findFakeCoin(int[] coins, int begin){
        int heap1, heap2, heap3, weight1 = 0, weight2 = 0;
        //递归终止条件 - 找到那一枚假币
        if (coins[0] == 1){
            return new int[]{begin};
        }
        //分堆
        if (coins[0] % 3 == 0){
            heap1 = heap2 = coins[0] / 3;
        }else {
            heap1 = heap2 = coins[0] / 3 + 1;
        }
        heap3 = coins[0] - heap1 - heap2;
        //获取第一堆和第二堆的总重量
        for (int i = 0; i < heap1 ; i++) {//计算第一堆总重量
            weight1 += coins[begin + i];
        }
        for (int i = heap1; i < heap1 + heap2; i++){//计算第二堆总重量
            weight2 += coins[begin + i];
        }
        //根据总重量判断在那一堆，并进入递归
        if (weight1 < weight2){// 假币在第一堆
            coins[0] = heap1;
            return findFakeCoin(coins, begin);
        }else if (weight1 > weight2){// 假币在第二堆
            coins[0] = heap2;
            begin = begin + heap1;
            return findFakeCoin(coins, begin);
        }else {// 假币在第三堆
            coins[0] = heap3;
            begin = begin + heap1 + heap2;
            return findFakeCoin(coins, begin);
        }
    }
}
